package com.leecode.exercise;


import com.sun.xml.internal.ws.util.StringUtils;

import java.util.Stack;

/**
 * 题目描述：给定一个合法的表达式字符串，其中只包含非负整数、运算符 +、-、*、/，以及空格。求表达式的值。
 * <p>
 * 假设表达式是 "3+5*2-8/2"
 * <p>
 * 解决办法：
 * <p>
 * 1) 使用两个栈，一个用于存储操作数，一个用于存储运算符。
 * 2) 遍历表达式字符串，对每个字符进行处理。
 * 3) 如果是数字，则将其解析并压入操作数栈。
 * 4) 如果是运算符，则与运算符栈的栈顶进行比较，如果当前运算符的优先级小于等于栈顶运算符的优先级，就进行计算，直到当前运算符的优先级大于栈顶运算符或者栈为空。然后将当前运算符入栈。
 * 5) 最终，将剩余的运算符和操作数进行计算，得到最终结果。
 */

public class ExpressionEvaluation {

    public static void main(String[] args) {

        //等价表达式：numsStack:
        String expression = "3+5*2-8/2";

        int result = calculate(expression);
        System.out.println("Result of expression " + expression + " is: " + result);

    }


    public static int calculate(String s) {
        //边界判断
        if (s.isEmpty()) {
            return 0;
        }

        //3+5*2-8/2

        Stack<Integer> numsStack = new Stack();
        Stack<Character> operStack = new Stack();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < s.length() && Character.isDigit(s.charAt(i))) {
                    num = 0 * num + (c - '0');
                    i++;
                }
                i--;
                numsStack.push(num);
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {  //字母
                while (!operStack.isEmpty() && hasHigherPrecedence(operStack.peek(), c)) {
                    evaluateAndPush(numsStack, operStack);
                }

                operStack.push(c);
            }
        }

        while (!operStack.isEmpty()) {
            evaluateAndPush(numsStack, operStack);
        }

        return numsStack.pop();
    }

    private static boolean hasHigherPrecedence(char op1, char op2) {
        if ((op1 == '*' || op1 == '/') && (op2 == '+' || op2 == '-')) {
            return true;
        }

        return false;
    }

    //计算表达式的值
    private static void evaluateAndPush(Stack<Integer> numsStack, Stack<Character> operStack) {
        char operator = operStack.pop();
        int num2 = numsStack.pop();
        int num1 = numsStack.pop();
        int result = performOperation(num1, num2, operator);
        numsStack.push(result);
    }

    //计算逻辑
    private static int performOperation(int operand1, int operand2, char operator) {
        switch (operator) {
            case '+':
                return operand1 + operand2;
            case '-':
                return operand1 - operand2;
            case '*':
                return operand1 * operand2;
            case '/':
                return operand1 / operand2;
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }

}
